﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    public class Solution26
    {
        #region 78. 子集
//        给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

//说明：解集不能包含重复的子集。

//示例:

//输入: nums = [1,2,3]
//        输出:
//[
//  [3],
//  [1],
//  [2],
//  [1,2,3],
//  [1,3],
//  [2,3],
//  [1,2],
//  []
        #endregion
        public IList<IList<int>> Subsets(int[] nums)
        {
            List<IList<int>> result = new List<IList<int>>();
            result.Add(new List<int>());
            Array.Sort(nums);
            for (int i = 0; i < nums.Length; i++)
            {
                List<IList<int>> newResult = new List<IList<int>>();
                foreach (var r in result)
                {
                    List<int> nr = new List<int>(r);
                    nr.Add(nums[i]);
                    newResult.Add(nr);
                }
                result.AddRange(newResult);
            }
            return result;
        }
    }
}
